home *** CD-ROM | disk | FTP | other *** search
/ CU Amiga Super CD-ROM 24 / CU Amiga Magazine's Super CD-ROM 24 (1998)(EMAP Images)(GB)(Track 1 of 2)[!][issue 1998-07].iso / CUCD / Utilities / vim-5.1 / src / undo.c < prev    next >
Encoding:
C/C++ Source or Header  |  1998-03-07  |  28.2 KB  |  1,120 lines
  1. /* vi:set ts=8 sts=4 sw=4:
  2.  *
  3.  * VIM - Vi IMproved    by Bram Moolenaar
  4.  *
  5.  * Do ":help uganda"  in Vim to read copying and usage conditions.
  6.  * Do ":help credits" in Vim to see a list of people who contributed.
  7.  */
  8.  
  9. /*
  10.  * undo.c: multi level undo facility
  11.  *
  12.  * The saved lines are stored in a list of lists (one for each buffer):
  13.  *
  14.  * b_u_oldhead------------------------------------------------+
  15.  *                                  |
  16.  *                                  V
  17.  *          +--------------+    +--------------+      +--------------+
  18.  * b_u_newhead--->| u_header     |    | u_header     |      | u_header     |
  19.  *          |    uh_next------>|     uh_next------>|    uh_next---->NULL
  20.  *       NULL<--------uh_prev  |<---------uh_prev  |<---------uh_prev  |
  21.  *          |    uh_entry |    |     uh_entry |      |    uh_entry |
  22.  *          +--------|-----+    +--------|-----+      +--------|-----+
  23.  *               |               |           |
  24.  *               V               V           V
  25.  *          +--------------+    +--------------+      +--------------+
  26.  *          | u_entry     |    | u_entry      |      | u_entry     |
  27.  *          |    ue_next  |    |     ue_next  |      |    ue_next  |
  28.  *          +--------|-----+    +--------|-----+      +--------|-----+
  29.  *               |               |           |
  30.  *               V               V           V
  31.  *          +--------------+          NULL          NULL
  32.  *          | u_entry     |
  33.  *          |    ue_next  |
  34.  *          +--------|-----+
  35.  *               |
  36.  *               V
  37.  *              etc.
  38.  *
  39.  * Each u_entry list contains the information for one undo or redo.
  40.  * curbuf->b_u_curhead points to the header of the last undo (the next redo),
  41.  * or is NULL if nothing has been undone.
  42.  *
  43.  * All data is allocated with u_alloc_line(), thus it will be freed as soon as
  44.  * we switch files!
  45.  */
  46.  
  47. #include "vim.h"
  48.  
  49. static void u_getbot __ARGS((void));
  50. static int u_savecommon __ARGS((linenr_t, linenr_t, linenr_t));
  51. static void u_doit __ARGS((int count));
  52. static void u_undoredo __ARGS((void));
  53. static void u_undo_end __ARGS((void));
  54. static void u_freelist __ARGS((struct u_header *));
  55. static void u_freeentry __ARGS((struct u_entry *, long));
  56.  
  57. static char_u *u_blockalloc __ARGS((long_u));
  58. static void u_free_line __ARGS((char_u *));
  59. static char_u *u_alloc_line __ARGS((unsigned));
  60. static char_u *u_save_line __ARGS((linenr_t));
  61.  
  62. static long    u_newcount, u_oldcount;
  63.  
  64. /*
  65.  * When 'u' flag included in 'cpoptions', we behave like vi.  Need to remember
  66.  * the action that "u" should do.
  67.  */
  68. static int    undo_undoes = FALSE;
  69.  
  70. /*
  71.  * save the current line for both the "u" and "U" command
  72.  */
  73.     int
  74. u_save_cursor()
  75. {
  76.     return (u_save((linenr_t)(curwin->w_cursor.lnum - 1),
  77.                       (linenr_t)(curwin->w_cursor.lnum + 1)));
  78. }
  79.  
  80. /*
  81.  * Save the lines between "top" and "bot" for both the "u" and "U" command.
  82.  * "top" may be 0 and bot may be curbuf->b_ml.ml_line_count + 1.
  83.  * Returns FAIL when lines could not be saved, OK otherwise.
  84.  */
  85.     int
  86. u_save(top, bot)
  87.     linenr_t top, bot;
  88. {
  89.     if (undo_off)
  90.     return OK;
  91.  
  92.     if (top > curbuf->b_ml.ml_line_count ||
  93.                 top >= bot || bot > curbuf->b_ml.ml_line_count + 1)
  94.     return FALSE;    /* rely on caller to do error messages */
  95.  
  96.     if (top + 2 == bot)
  97.     u_saveline((linenr_t)(top + 1));
  98.  
  99.     return (u_savecommon(top, bot, (linenr_t)0));
  100. }
  101.  
  102. /*
  103.  * save the line "lnum" (used by :s command)
  104.  * The line is replaced, so the new bottom line is lnum + 1.
  105.  */
  106.     int
  107. u_savesub(lnum)
  108.     linenr_t    lnum;
  109. {
  110.     if (undo_off)
  111.     return OK;
  112.  
  113.     return (u_savecommon(lnum - 1, lnum + 1, lnum + 1));
  114. }
  115.  
  116. /*
  117.  * a new line is inserted before line "lnum" (used by :s command)
  118.  * The line is inserted, so the new bottom line is lnum + 1.
  119.  */
  120.     int
  121. u_inssub(lnum)
  122.     linenr_t    lnum;
  123. {
  124.     if (undo_off)
  125.     return OK;
  126.  
  127.     return (u_savecommon(lnum - 1, lnum, lnum + 1));
  128. }
  129.  
  130. /*
  131.  * save the lines "lnum" - "lnum" + nlines (used by delete command)
  132.  * The lines are deleted, so the new bottom line is lnum, unless the buffer
  133.  * becomes empty.
  134.  */
  135.     int
  136. u_savedel(lnum, nlines)
  137.     linenr_t    lnum;
  138.     long    nlines;
  139. {
  140.     if (undo_off)
  141.     return OK;
  142.  
  143.     return (u_savecommon(lnum - 1, lnum + nlines,
  144.             nlines == curbuf->b_ml.ml_line_count ? 2 : lnum));
  145. }
  146.  
  147.     static int
  148. u_savecommon(top, bot, newbot)
  149.     linenr_t top, bot;
  150.     linenr_t newbot;
  151. {
  152.     linenr_t        lnum;
  153.     long        i;
  154.     struct u_header *uhp;
  155.     struct u_entry  *uep;
  156.     long        size;
  157.  
  158.     /*
  159.      * if curbuf->b_u_synced == TRUE make a new header
  160.      */
  161.     if (curbuf->b_u_synced)
  162.     {
  163.     /*
  164.      * if we undid more than we redid, free the entry lists before and
  165.      * including curbuf->b_u_curhead
  166.      */
  167.     while (curbuf->b_u_curhead != NULL)
  168.         u_freelist(curbuf->b_u_newhead);
  169.  
  170.     /*
  171.      * free headers to keep the size right
  172.      */
  173.     while (curbuf->b_u_numhead > p_ul && curbuf->b_u_oldhead != NULL)
  174.         u_freelist(curbuf->b_u_oldhead);
  175.  
  176.     if (p_ul < 0)        /* no undo at all */
  177.         return OK;
  178.  
  179.     /*
  180.      * make a new header entry
  181.      */
  182.     uhp = (struct u_header *)u_alloc_line((unsigned)
  183.                              sizeof(struct u_header));
  184.     if (uhp == NULL)
  185.         goto nomem;
  186.     uhp->uh_prev = NULL;
  187.     uhp->uh_next = curbuf->b_u_newhead;
  188.     if (curbuf->b_u_newhead != NULL)
  189.         curbuf->b_u_newhead->uh_prev = uhp;
  190.     uhp->uh_entry = NULL;
  191.     uhp->uh_cursor = curwin->w_cursor;    /* save cursor pos. for undo */
  192.  
  193.     /* save changed and buffer empty flag for undo */
  194.     uhp->uh_flags = (curbuf->b_changed ? UH_CHANGED : 0) +
  195.                ((curbuf->b_ml.ml_flags & ML_EMPTY) ? UH_EMPTYBUF : 0);
  196.  
  197.     /* save named marks for undo */
  198.     vim_memmove(uhp->uh_namedm, curbuf->b_namedm, sizeof(FPOS) * NMARKS);
  199.     curbuf->b_u_newhead = uhp;
  200.     if (curbuf->b_u_oldhead == NULL)
  201.         curbuf->b_u_oldhead = uhp;
  202.     ++curbuf->b_u_numhead;
  203.     }
  204.     else    /* find line number for ue_bot for previous u_save() */
  205.     u_getbot();
  206.  
  207.     size = bot - top - 1;
  208. #if !defined(UNIX) && !defined(DJGPP) && !defined(WIN32) && !defined(__EMX__)
  209.     /*
  210.      * With Amiga and MSDOS 16 bit we can't handle big undo's, because
  211.      * then u_alloc_line would have to allocate a block larger than 32K
  212.      */
  213.     if (size >= 8000)
  214.     goto nomem;
  215. #endif
  216.  
  217.     /*
  218.      * add lines in front of entry list
  219.      */
  220.     uep = (struct u_entry *)u_alloc_line((unsigned)sizeof(struct u_entry));
  221.     if (uep == NULL)
  222.     goto nomem;
  223.  
  224.     uep->ue_size = size;
  225.     uep->ue_top = top;
  226.     uep->ue_lcount = 0;
  227.     if (newbot)
  228.     uep->ue_bot = newbot;
  229.     /*
  230.      * Use 0 for ue_bot if bot is below last line.
  231.      * Otherwise we have to compute ue_bot later.
  232.      */
  233.     else if (bot > curbuf->b_ml.ml_line_count)
  234.     uep->ue_bot = 0;
  235.     else
  236.     uep->ue_lcount = curbuf->b_ml.ml_line_count;
  237.  
  238.     if (size)
  239.     {
  240.     if ((uep->ue_array = (char_u **)u_alloc_line((unsigned)(sizeof(char_u *) * size))) == NULL)
  241.     {
  242.         u_freeentry(uep, 0L);
  243.         goto nomem;
  244.     }
  245.     for (i = 0, lnum = top + 1; i < size; ++i)
  246.     {
  247.         if ((uep->ue_array[i] = u_save_line(lnum++)) == NULL)
  248.         {
  249.         u_freeentry(uep, i);
  250.         goto nomem;
  251.         }
  252.     }
  253.     }
  254.     uep->ue_next = curbuf->b_u_newhead->uh_entry;
  255.     curbuf->b_u_newhead->uh_entry = uep;
  256.     curbuf->b_u_synced = FALSE;
  257.     undo_undoes = FALSE;
  258.  
  259.     return OK;
  260.  
  261. nomem:
  262.     if (ask_yesno((char_u *)"No undo possible; continue anyway", TRUE) == 'y')
  263.     {
  264.     undo_off = TRUE;        /* will be reset when character typed */
  265.     return OK;
  266.     }
  267.     do_outofmem_msg();
  268.     return FAIL;
  269. }
  270.  
  271. /*
  272.  * If 'cpoptions' contains 'u': Undo the previous undo or redo (vi compatible).
  273.  * If 'cpoptions' does not contain 'u': Always undo.
  274.  */
  275.     void
  276. u_undo(count)
  277.     int count;
  278. {
  279.     /*
  280.      * If we get an undo command while executing a macro, we behave like the
  281.      * original vi. If this happens twice in one macro the result will not
  282.      * be compatible.
  283.      */
  284.     if (curbuf->b_u_synced == FALSE)
  285.     {
  286.     u_sync();
  287.     count = 1;
  288.     }
  289.  
  290.     if (vim_strchr(p_cpo, CPO_UNDO) == NULL)
  291.     undo_undoes = TRUE;
  292.     else
  293.     undo_undoes = !undo_undoes;
  294.     u_doit(count);
  295. }
  296.  
  297. /*
  298.  * If 'cpoptions' contains 'u': Repeat the previous undo or redo.
  299.  * If 'cpoptions' does not contain 'u': Always redo.
  300.  */
  301.     void
  302. u_redo(count)
  303.     int count;
  304. {
  305.     if (vim_strchr(p_cpo, CPO_UNDO) == NULL)
  306.     undo_undoes = FALSE;
  307.     u_doit(count);
  308. }
  309.  
  310. /*
  311.  * Undo or redo, depending on 'undo_undoes', 'count' times.
  312.  */
  313.     static void
  314. u_doit(count)
  315.     int count;
  316. {
  317.     u_newcount = 0;
  318.     u_oldcount = 0;
  319.     while (count--)
  320.     {
  321.     if (undo_undoes)
  322.     {
  323.         if (curbuf->b_u_curhead == NULL)        /* first undo */
  324.         curbuf->b_u_curhead = curbuf->b_u_newhead;
  325.         else if (p_ul > 0)                /* multi level undo */
  326.         /* get next undo */
  327.         curbuf->b_u_curhead = curbuf->b_u_curhead->uh_next;
  328.         /* nothing to undo */
  329.         if (curbuf->b_u_numhead == 0 || curbuf->b_u_curhead == NULL)
  330.         {
  331.         /* stick curbuf->b_u_curhead at end */
  332.         curbuf->b_u_curhead = curbuf->b_u_oldhead;
  333.         beep_flush();
  334.         break;
  335.         }
  336.  
  337.         u_undoredo();
  338.     }
  339.     else
  340.     {
  341.         if (curbuf->b_u_curhead == NULL || p_ul <= 0)
  342.         {
  343.         beep_flush();    /* nothing to redo */
  344.         break;
  345.         }
  346.  
  347.         u_undoredo();
  348.         /* advance for next redo */
  349.         curbuf->b_u_curhead = curbuf->b_u_curhead->uh_prev;
  350.     }
  351.     }
  352.     u_undo_end();
  353. }
  354.  
  355. /*
  356.  * u_undoredo: common code for undo and redo
  357.  *
  358.  * The lines in the file are replaced by the lines in the entry list at
  359.  * curbuf->b_u_curhead. The replaced lines in the file are saved in the entry
  360.  * list for the next undo/redo.
  361.  */
  362.     static void
  363. u_undoredo()
  364. {
  365.     char_u    **newarray = NULL;
  366.     linenr_t    oldsize;
  367.     linenr_t    newsize;
  368.     linenr_t    top, bot;
  369.     linenr_t    lnum;
  370.     linenr_t    newlnum = MAXLNUM;
  371.     long    i;
  372.     struct u_entry *uep, *nuep;
  373.     struct u_entry *newlist = NULL;
  374.     int        old_flags;
  375.     int        new_flags;
  376.     FPOS    namedm[NMARKS];
  377.     int        empty_buffer;            /* buffer became empty */
  378.  
  379.     old_flags = curbuf->b_u_curhead->uh_flags;
  380.     new_flags = (curbuf->b_changed ? UH_CHANGED : 0) +
  381.            ((curbuf->b_ml.ml_flags & ML_EMPTY) ? UH_EMPTYBUF : 0);
  382.     if (old_flags & UH_CHANGED)
  383.     CHANGED;
  384.     else
  385.     UNCHANGED(curbuf);
  386.     setpcmark();
  387.     changed_line_abv_curs();    /* need to recompute cursor posn on screen */
  388.  
  389.     /*
  390.      * save marks before undo/redo
  391.      */
  392.     vim_memmove(namedm, curbuf->b_namedm, sizeof(FPOS) * NMARKS);
  393.     curbuf->b_op_start.lnum = curbuf->b_ml.ml_line_count;
  394.     curbuf->b_op_start.col = 0;
  395.     curbuf->b_op_end.lnum = 0;
  396.     curbuf->b_op_end.col = 0;
  397.  
  398.     for (uep = curbuf->b_u_curhead->uh_entry; uep != NULL; uep = nuep)
  399.     {
  400.     top = uep->ue_top;
  401.     bot = uep->ue_bot;
  402.     if (bot == 0)
  403.         bot = curbuf->b_ml.ml_line_count + 1;
  404.     if (top > curbuf->b_ml.ml_line_count || top >= bot || bot > curbuf->b_ml.ml_line_count + 1)
  405.     {
  406.         EMSG("u_undo: line numbers wrong");
  407.         CHANGED;        /* don't want UNCHANGED now */
  408.         return;
  409.     }
  410.  
  411.     if (top < newlnum)
  412.     {
  413.         newlnum = top;
  414.         curwin->w_cursor.lnum = top + 1;
  415.     }
  416.     oldsize = bot - top - 1;    /* number of lines before undo */
  417.     newsize = uep->ue_size;        /* number of lines after undo */
  418.  
  419.     empty_buffer = FALSE;
  420.  
  421.     /* delete the lines between top and bot and save them in newarray */
  422.     if (oldsize)
  423.     {
  424.         if ((newarray = (char_u **)u_alloc_line((unsigned)(sizeof(char_u *) * oldsize))) == NULL)
  425.         {
  426.         do_outofmem_msg();
  427.         /*
  428.          * We have messed up the entry list, repair is impossible.
  429.          * we have to free the rest of the list.
  430.          */
  431.         while (uep != NULL)
  432.         {
  433.             nuep = uep->ue_next;
  434.             u_freeentry(uep, uep->ue_size);
  435.             uep = nuep;
  436.         }
  437.         break;
  438.         }
  439.         /* delete backwards, it goes faster in most cases */
  440.         for (lnum = bot - 1, i = oldsize; --i >= 0; --lnum)
  441.         {
  442.             /* what can we do when we run out of memory? */
  443.         if ((newarray[i] = u_save_line(lnum)) == NULL)
  444.             do_outofmem_msg();
  445.             /* remember we deleted the last line in the buffer, and a
  446.              * dummy empty line will be inserted */
  447.         if (curbuf->b_ml.ml_line_count == 1)
  448.             empty_buffer = TRUE;
  449.         ml_delete(lnum, FALSE);
  450.         }
  451.     }
  452.  
  453.     /* insert the lines in u_array between top and bot */
  454.     if (newsize)
  455.     {
  456.         for (lnum = top, i = 0; i < newsize; ++i, ++lnum)
  457.         {
  458.         /*
  459.          * If the file is empty, there is an empty line 1 that we
  460.          * should get rid of, by replacing it with the new line
  461.          */
  462.         if (empty_buffer && lnum == 0)
  463.             ml_replace((linenr_t)1, uep->ue_array[i], TRUE);
  464.         else
  465.             ml_append(lnum, uep->ue_array[i], (colnr_t)0, FALSE);
  466.         u_free_line(uep->ue_array[i]);
  467.         }
  468.         u_free_line((char_u *)uep->ue_array);
  469.     }
  470.  
  471.     /* adjust marks */
  472.     if (oldsize != newsize)
  473.     {
  474.         mark_adjust(top + 1, top + oldsize, (linenr_t)MAXLNUM,
  475.                            (long)newsize - (long)oldsize);
  476.         if (curbuf->b_op_start.lnum > top + oldsize)
  477.         curbuf->b_op_start.lnum += newsize - oldsize;
  478.         if (curbuf->b_op_end.lnum > top + oldsize)
  479.         curbuf->b_op_end.lnum += newsize - oldsize;
  480.     }
  481.     /* set '[ and '] mark */
  482.     if (top + 1 < curbuf->b_op_start.lnum)
  483.         curbuf->b_op_start.lnum = top + 1;
  484.     if (newsize == 0 && top + 1 > curbuf->b_op_end.lnum)
  485.         curbuf->b_op_end.lnum = top + 1;
  486.     else if (top + newsize > curbuf->b_op_end.lnum)
  487.         curbuf->b_op_end.lnum = top + newsize;
  488.  
  489.     u_newcount += newsize;
  490.     u_oldcount += oldsize;
  491.     uep->ue_size = oldsize;
  492.     uep->ue_array = newarray;
  493.     uep->ue_bot = top + newsize + 1;
  494.  
  495.     /*
  496.      * insert this entry in front of the new entry list
  497.      */
  498.     nuep = uep->ue_next;
  499.     uep->ue_next = newlist;
  500.     newlist = uep;
  501.     }
  502.  
  503.     curbuf->b_u_curhead->uh_entry = newlist;
  504.     curbuf->b_u_curhead->uh_flags = new_flags;
  505.     if ((old_flags & UH_EMPTYBUF) && bufempty())
  506.     curbuf->b_ml.ml_flags |= ML_EMPTY;
  507.  
  508.     /*
  509.      * restore marks from before undo/redo
  510.      */
  511.     for (i = 0; i < NMARKS; ++i)
  512.     if (curbuf->b_u_curhead->uh_namedm[i].lnum)
  513.     {
  514.         curbuf->b_namedm[i] = curbuf->b_u_curhead->uh_namedm[i];
  515.         curbuf->b_u_curhead->uh_namedm[i] = namedm[i];
  516.     }
  517.  
  518.     /*
  519.      * If the cursor is only off by one line, put it at the same position as
  520.      * before starting the change (for the "o" command).
  521.      * Otherwise the cursor should go to the first undone line.
  522.      */
  523.     if (curbuf->b_u_curhead->uh_cursor.lnum + 1 == curwin->w_cursor.lnum &&
  524.                             curwin->w_cursor.lnum > 1)
  525.     --curwin->w_cursor.lnum;
  526.     if (curbuf->b_u_curhead->uh_cursor.lnum == curwin->w_cursor.lnum)
  527.     curwin->w_cursor.col = curbuf->b_u_curhead->uh_cursor.col;
  528.     else if (curwin->w_cursor.lnum <= curbuf->b_ml.ml_line_count)
  529.     beginline(BL_SOL | BL_FIX);
  530.     /* We still seem to need the case below because sometimes we get here with
  531.      * the current cursor line being one past the end (eg after adding lines
  532.      * at the end of the file, and then undoing it).  Is it fair enough that
  533.      * this happens? -- webb
  534.      */
  535.     else
  536.     curwin->w_cursor.col = 0;
  537.  
  538.     /* Make sure the cursor is on an existing line and column. */
  539.     adjust_cursor();
  540. }
  541.  
  542. /*
  543.  * If we deleted or added lines, report the number of less/more lines.
  544.  * Otherwise, report the number of changes (this may be incorrect
  545.  * in some cases, but it's better than nothing).
  546.  */
  547.     static void
  548. u_undo_end()
  549. {
  550.     if ((u_oldcount -= u_newcount) != 0)
  551.     msgmore(-u_oldcount);
  552.     else if (u_newcount > p_report)
  553.     smsg((char_u *)"%ld change%s", u_newcount, plural(u_newcount));
  554.  
  555.     update_topline();
  556.     update_curbuf(NOT_VALID);    /* need to update all windows in this buffer */
  557. }
  558.  
  559. /*
  560.  * u_sync: stop adding to the current entry list
  561.  */
  562.     void
  563. u_sync()
  564. {
  565.     if (curbuf->b_u_synced)
  566.     return;            /* already synced */
  567.     u_getbot();            /* compute ue_bot of previous u_save */
  568.     curbuf->b_u_curhead = NULL;
  569. }
  570.  
  571. /*
  572.  * Called after writing the file and setting b_changed to FALSE.
  573.  * Now an undo means that the buffer is modified.
  574.  */
  575.     void
  576. u_unchanged(buf)
  577.     BUF        *buf;
  578. {
  579.     struct u_header    *uh;
  580.  
  581.     for (uh = buf->b_u_newhead; uh; uh = uh->uh_next)
  582.     uh->uh_flags |= UH_CHANGED;
  583.     buf->b_did_warn = FALSE;
  584. }
  585.  
  586. /*
  587.  * u_getbot(): compute the line number of the previous u_save
  588.  *        It is called only when b_u_synced is FALSE.
  589.  */
  590.     static void
  591. u_getbot()
  592. {
  593.     struct u_entry    *uep;
  594.  
  595.     if (curbuf->b_u_newhead == NULL ||
  596.                 (uep = curbuf->b_u_newhead->uh_entry) == NULL)
  597.     {
  598.     EMSG("undo list corrupt");
  599.     return;
  600.     }
  601.  
  602.     if (uep->ue_lcount != 0)
  603.     {
  604.     /*
  605.      * the new ue_bot is computed from the number of lines that has been
  606.      * inserted (0 - deleted) since calling u_save. This is equal to the old
  607.      * line count subtracted from the current line count.
  608.      */
  609.     uep->ue_bot = uep->ue_top + uep->ue_size + 1 +
  610.                 (curbuf->b_ml.ml_line_count - uep->ue_lcount);
  611.     if (uep->ue_bot < 1 || uep->ue_bot > curbuf->b_ml.ml_line_count)
  612.     {
  613.         EMSG("undo line missing");
  614.         uep->ue_bot = uep->ue_top + 1;  /* assume all lines deleted, will
  615.                          * get all the old lines back
  616.                          * without deleting the current
  617.                          * ones */
  618.     }
  619.     uep->ue_lcount = 0;
  620.     }
  621.  
  622.     curbuf->b_u_synced = TRUE;
  623. }
  624.  
  625. /*
  626.  * u_freelist: free one entry list and adjust the pointers
  627.  */
  628.     static void
  629. u_freelist(uhp)
  630.     struct u_header *uhp;
  631. {
  632.     struct u_entry    *uep, *nuep;
  633.  
  634.     for (uep = uhp->uh_entry; uep != NULL; uep = nuep)
  635.     {
  636.     nuep = uep->ue_next;
  637.     u_freeentry(uep, uep->ue_size);
  638.     }
  639.  
  640.     if (curbuf->b_u_curhead == uhp)
  641.     curbuf->b_u_curhead = NULL;
  642.  
  643.     if (uhp->uh_next == NULL)
  644.     curbuf->b_u_oldhead = uhp->uh_prev;
  645.     else
  646.     uhp->uh_next->uh_prev = uhp->uh_prev;
  647.  
  648.     if (uhp->uh_prev == NULL)
  649.     curbuf->b_u_newhead = uhp->uh_next;
  650.     else
  651.     uhp->uh_prev->uh_next = uhp->uh_next;
  652.  
  653.     u_free_line((char_u *)uhp);
  654.     --curbuf->b_u_numhead;
  655. }
  656.  
  657. /*
  658.  * free entry 'uep' and 'n' lines in uep->ue_array[]
  659.  */
  660.     static void
  661. u_freeentry(uep, n)
  662.     struct u_entry  *uep;
  663.     long        n;
  664. {
  665.     while (n)
  666.     u_free_line(uep->ue_array[--n]);
  667.     u_free_line((char_u *)uep);
  668. }
  669.  
  670. /*
  671.  * invalidate the undo buffer; called when storage has already been released
  672.  */
  673.     void
  674. u_clearall(buf)
  675.     BUF        *buf;
  676. {
  677.     buf->b_u_newhead = buf->b_u_oldhead = buf->b_u_curhead = NULL;
  678.     buf->b_u_synced = TRUE;
  679.     buf->b_u_numhead = 0;
  680.     buf->b_u_line_ptr = NULL;
  681.     buf->b_u_line_lnum = 0;
  682. }
  683.  
  684. /*
  685.  * save the line "lnum" for the "U" command
  686.  */
  687.     void
  688. u_saveline(lnum)
  689.     linenr_t lnum;
  690. {
  691.     if (lnum == curbuf->b_u_line_lnum)        /* line is already saved */
  692.     return;
  693.     if (lnum < 1 || lnum > curbuf->b_ml.ml_line_count)    /* should never happen */
  694.     return;
  695.     u_clearline();
  696.     curbuf->b_u_line_lnum = lnum;
  697.     if (curwin->w_cursor.lnum == lnum)
  698.     curbuf->b_u_line_colnr = curwin->w_cursor.col;
  699.     else
  700.     curbuf->b_u_line_colnr = 0;
  701.     if ((curbuf->b_u_line_ptr = u_save_line(lnum)) == NULL)
  702.     do_outofmem_msg();
  703. }
  704.  
  705. /*
  706.  * clear the line saved for the "U" command
  707.  * (this is used externally for crossing a line while in insert mode)
  708.  */
  709.     void
  710. u_clearline()
  711. {
  712.     if (curbuf->b_u_line_ptr != NULL)
  713.     {
  714.     u_free_line(curbuf->b_u_line_ptr);
  715.     curbuf->b_u_line_ptr = NULL;
  716.     curbuf->b_u_line_lnum = 0;
  717.     }
  718. }
  719.  
  720. /*
  721.  * Implementation of the "U" command.
  722.  * Differentiation from vi: "U" can be undone with the next "U".
  723.  * We also allow the cursor to be in another line.
  724.  */
  725.     void
  726. u_undoline()
  727. {
  728.     colnr_t t;
  729.     char_u  *oldp;
  730.  
  731.     if (undo_off)
  732.     return;
  733.  
  734.     if (curbuf->b_u_line_ptr == NULL ||
  735.             curbuf->b_u_line_lnum > curbuf->b_ml.ml_line_count)
  736.     {
  737.     beep_flush();
  738.     return;
  739.     }
  740.     /* first save the line for the 'u' command */
  741.     if (u_savecommon(curbuf->b_u_line_lnum - 1,
  742.                 curbuf->b_u_line_lnum + 1, (linenr_t)0) == FAIL)
  743.     return;
  744.     oldp = u_save_line(curbuf->b_u_line_lnum);
  745.     if (oldp == NULL)
  746.     {
  747.     do_outofmem_msg();
  748.     return;
  749.     }
  750.     ml_replace(curbuf->b_u_line_lnum, curbuf->b_u_line_ptr, TRUE);
  751.     u_free_line(curbuf->b_u_line_ptr);
  752.     curbuf->b_u_line_ptr = oldp;
  753.  
  754.     t = curbuf->b_u_line_colnr;
  755.     if (curwin->w_cursor.lnum == curbuf->b_u_line_lnum)
  756.     curbuf->b_u_line_colnr = curwin->w_cursor.col;
  757.     changed_cline_bef_curs();
  758.     curwin->w_cursor.col = t;
  759.     curwin->w_cursor.lnum = curbuf->b_u_line_lnum;
  760.     approximate_botline();    /* w_botline may have changed a bit */
  761.     update_screen(VALID_TO_CURSCHAR);
  762. }
  763.  
  764. /*
  765.  * storage allocation for the undo lines and blocks of the current file
  766.  */
  767.  
  768. /*
  769.  * Memory is allocated in relatively large blocks. These blocks are linked
  770.  * in the allocated block list, headed by curbuf->b_block_head. They are all
  771.  * freed when abandoning a file, so we don't have to free every single line.
  772.  * The list is kept sorted on memory address.
  773.  * block_alloc() allocates a block.
  774.  * m_blockfree() frees all blocks.
  775.  *
  776.  * The available chunks of memory are kept in free chunk lists. There is
  777.  * one free list for each block of allocated memory. The list is kept sorted
  778.  * on memory address.
  779.  * u_alloc_line() gets a chunk from the free lists.
  780.  * u_free_line() returns a chunk to the free lists.
  781.  * curbuf->b_m_search points to the chunk before the chunk that was
  782.  * freed/allocated the last time.
  783.  * curbuf->b_mb_current points to the b_head where curbuf->b_m_search
  784.  * points into the free list.
  785.  *
  786.  *
  787.  *  b_block_head     /---> block #1    /---> block #2
  788.  *     mb_next ---/        mb_next ---/       mb_next ---> NULL
  789.  *     mb_info        mb_info           mb_info
  790.  *        |               |          |
  791.  *        V               V          V
  792.  *      NULL        free chunk #1.1      free chunk #2.1
  793.  *                   |          |
  794.  *                   V          V
  795.  *            free chunk #1.2         NULL
  796.  *                   |
  797.  *                   V
  798.  *                  NULL
  799.  *
  800.  * When a single free chunk list would have been used, it could take a lot
  801.  * of time in u_free_line() to find the correct place to insert a chunk in the
  802.  * free list. The single free list would become very long when many lines are
  803.  * changed (e.g. with :%s/^M$//).
  804.  */
  805.  
  806.     /*
  807.      * this blocksize is used when allocating new lines
  808.      */
  809. #define MEMBLOCKSIZE 2044
  810.  
  811. /*
  812.  * The size field contains the size of the chunk, including the size field
  813.  * itself.
  814.  *
  815.  * When the chunk is not in-use it is preceded with the m_info structure.
  816.  * The m_next field links it in one of the free chunk lists.
  817.  *
  818.  * On most unix systems structures have to be longword (32 or 64 bit) aligned.
  819.  * On most other systems they are short (16 bit) aligned.
  820.  */
  821.  
  822. /* the structure definitions are now in structs.h */
  823.  
  824. #ifdef ALIGN_LONG
  825.     /* size of m_size */
  826. # define M_OFFSET (sizeof(long_u))
  827. #else
  828.     /* size of m_size */
  829. # define M_OFFSET (sizeof(short_u))
  830. #endif
  831.  
  832. /*
  833.  * Allocate a block of memory and link it in the allocated block list.
  834.  */
  835.     static char_u *
  836. u_blockalloc(size)
  837.     long_u  size;
  838. {
  839.     struct m_block *p;
  840.     struct m_block *mp, *next;
  841.  
  842.     p = (struct m_block *)lalloc(size + sizeof(struct m_block), FALSE);
  843.     if (p != NULL)
  844.     {
  845.      /* Insert the block into the allocated block list, keeping it
  846.             sorted on address. */
  847.     for (mp = &curbuf->b_block_head;
  848.         (next = mp->mb_next) != NULL && next < p;
  849.             mp = next)
  850.         ;
  851.     p->mb_next = next;        /* link in block list */
  852.     mp->mb_next = p;
  853.     p->mb_info.m_next = NULL;    /* clear free list */
  854.     p->mb_info.m_size = 0;
  855.     curbuf->b_mb_current = p;    /* remember current block */
  856.     curbuf->b_m_search = NULL;
  857.     p++;                /* return usable memory */
  858.     }
  859.     return (char_u *)p;
  860. }
  861.  
  862. /*
  863.  * free all allocated memory blocks for the buffer 'buf'
  864.  */
  865.     void
  866. u_blockfree(buf)
  867.     BUF        *buf;
  868. {
  869.     struct m_block  *p, *np;
  870.  
  871.     for (p = buf->b_block_head.mb_next; p != NULL; p = np)
  872.     {
  873.     np = p->mb_next;
  874.     vim_free(p);
  875.     }
  876.     buf->b_block_head.mb_next = NULL;
  877.     buf->b_m_search = NULL;
  878.     buf->b_mb_current = NULL;
  879. }
  880.  
  881. /*
  882.  * Free a chunk of memory.
  883.  * Insert the chunk into the correct free list, keeping it sorted on address.
  884.  */
  885.     static void
  886. u_free_line(ptr)
  887.     char_u *ptr;
  888. {
  889.     info_t        *next;
  890.     info_t        *prev, *curr;
  891.     info_t        *mp;
  892.     struct m_block    *nextb;
  893.  
  894.     if (ptr == NULL || ptr == IObuff)
  895.     return;    /* illegal address can happen in out-of-memory situations */
  896.  
  897.     mp = (info_t *)(ptr - M_OFFSET);
  898.  
  899.     /* find block where chunk could be a part off */
  900.     /* if we change curbuf->b_mb_current, curbuf->b_m_search is set to NULL */
  901.     if (curbuf->b_mb_current == NULL || mp < (info_t *)curbuf->b_mb_current)
  902.     {
  903.     curbuf->b_mb_current = curbuf->b_block_head.mb_next;
  904.     curbuf->b_m_search = NULL;
  905.     }
  906.     if ((nextb = curbuf->b_mb_current->mb_next) != NULL && (info_t *)nextb < mp)
  907.     {
  908.     curbuf->b_mb_current = nextb;
  909.     curbuf->b_m_search = NULL;
  910.     }
  911.     while ((nextb = curbuf->b_mb_current->mb_next) != NULL &&
  912.                              (info_t *)nextb < mp)
  913.     curbuf->b_mb_current = nextb;
  914.  
  915.     curr = NULL;
  916.     /*
  917.      * If mp is smaller than curbuf->b_m_search->m_next go to the start of
  918.      * the free list
  919.      */
  920.     if (curbuf->b_m_search == NULL || mp < (curbuf->b_m_search->m_next))
  921.     next = &(curbuf->b_mb_current->mb_info);
  922.     else
  923.     next = curbuf->b_m_search;
  924.     /*
  925.      * The following loop is executed very often.
  926.      * Therefore it has been optimized at the cost of readability.
  927.      * Keep it fast!
  928.      */
  929. #ifdef SLOW_BUT_EASY_TO_READ
  930.     do
  931.     {
  932.     prev = curr;
  933.     curr = next;
  934.     next = next->m_next;
  935.     }
  936.     while (mp > next && next != NULL);
  937. #else
  938.     do                        /* first, middle, last */
  939.     {
  940.     prev = next->m_next;            /* curr, next, prev */
  941.     if (prev == NULL || mp <= prev)
  942.     {
  943.         prev = curr;
  944.         curr = next;
  945.         next = next->m_next;
  946.         break;
  947.     }
  948.     curr = prev->m_next;            /* next, prev, curr */
  949.     if (curr == NULL || mp <= curr)
  950.     {
  951.         prev = next;
  952.         curr = prev->m_next;
  953.         next = curr->m_next;
  954.         break;
  955.     }
  956.     next = curr->m_next;            /* prev, curr, next */
  957.     }
  958.     while (mp > next && next != NULL);
  959. #endif
  960.  
  961.     /* if *mp and *next are concatenated, join them into one chunk */
  962.     if ((char_u *)mp + mp->m_size == (char_u *)next)
  963.     {
  964.     mp->m_size += next->m_size;
  965.     mp->m_next = next->m_next;
  966.     }
  967.     else
  968.     mp->m_next = next;
  969.  
  970.     /* if *curr and *mp are concatenated, join them */
  971.     if (prev != NULL && (char_u *)curr + curr->m_size == (char_u *)mp)
  972.     {
  973.     curr->m_size += mp->m_size;
  974.     curr->m_next = mp->m_next;
  975.     curbuf->b_m_search = prev;
  976.     }
  977.     else
  978.     {
  979.     curr->m_next = mp;
  980.     curbuf->b_m_search = curr;  /* put curbuf->b_m_search before freed
  981.                        chunk */
  982.     }
  983. }
  984.  
  985. /*
  986.  * Allocate and initialize a new line structure with room for at least
  987.  * 'size' characters plus a terminating NUL.
  988.  */
  989.     static char_u *
  990. u_alloc_line(size)
  991.     unsigned        size;
  992. {
  993.     info_t        *mp, *mprev, *mp2;
  994.     struct m_block  *mbp;
  995.     int            size_align;
  996.  
  997.     /*
  998.      * Add room for size field and trailing NUL byte.
  999.      * Adjust for minimal size (must be able to store info_t
  1000.      * plus a trailing NUL, so the chunk can be released again)
  1001.      */
  1002.     size += M_OFFSET + 1;
  1003.     if (size < sizeof(info_t) + 1)
  1004.       size = sizeof(info_t) + 1;
  1005.  
  1006.     /*
  1007.      * round size up for alignment
  1008.      */
  1009.     size_align = (size + ALIGN_MASK) & ~ALIGN_MASK;
  1010.  
  1011.     /*
  1012.      * If curbuf->b_m_search is NULL (uninitialized free list) start at
  1013.      * curbuf->b_block_head
  1014.      */
  1015.     if (curbuf->b_mb_current == NULL || curbuf->b_m_search == NULL)
  1016.     {
  1017.     curbuf->b_mb_current = &curbuf->b_block_head;
  1018.     curbuf->b_m_search = &(curbuf->b_block_head.mb_info);
  1019.     }
  1020.  
  1021.     /* search for space in free list */
  1022.     mprev = curbuf->b_m_search;
  1023.     mbp = curbuf->b_mb_current;
  1024.     mp = curbuf->b_m_search->m_next;
  1025.     if (mp == NULL)
  1026.     {
  1027.     if (mbp->mb_next)
  1028.         mbp = mbp->mb_next;
  1029.     else
  1030.         mbp = &curbuf->b_block_head;
  1031.     mp = curbuf->b_m_search = &(mbp->mb_info);
  1032.     }
  1033.     while (mp->m_size < size)
  1034.     {
  1035.     if (mp == curbuf->b_m_search)        /* back where we started in free
  1036.                            chunk list */
  1037.     {
  1038.         if (mbp->mb_next)
  1039.         mbp = mbp->mb_next;
  1040.         else
  1041.         mbp = &curbuf->b_block_head;
  1042.         mp = curbuf->b_m_search = &(mbp->mb_info);
  1043.         if (mbp == curbuf->b_mb_current)    /* back where we started in
  1044.                            block list */
  1045.         {
  1046.         int    n = (size_align > (MEMBLOCKSIZE / 4)
  1047.                          ? size_align : MEMBLOCKSIZE);
  1048.  
  1049.         mp = (info_t *)u_blockalloc((long_u)n);
  1050.         if (mp == NULL)
  1051.             return (NULL);
  1052.         mp->m_size = n;
  1053.         u_free_line((char_u *)mp + M_OFFSET);
  1054.         mp = curbuf->b_m_search;
  1055.         mbp = curbuf->b_mb_current;
  1056.         }
  1057.     }
  1058.     mprev = mp;
  1059.     if ((mp = mp->m_next) == NULL)        /* at end of the list */
  1060.         mp = &(mbp->mb_info);        /* wrap around to begin */
  1061.     }
  1062.  
  1063.     /* if the chunk we found is large enough, split it up in two */
  1064.     if ((long)mp->m_size - size_align >= (long)(sizeof(info_t) + 1))
  1065.     {
  1066.     mp2 = (info_t *)((char_u *)mp + size_align);
  1067.     mp2->m_size = mp->m_size - size_align;
  1068.     mp2->m_next = mp->m_next;
  1069.     mprev->m_next = mp2;
  1070.     mp->m_size = size_align;
  1071.     }
  1072.     else            /* remove *mp from the free list */
  1073.     {
  1074.     mprev->m_next = mp->m_next;
  1075.     }
  1076.     curbuf->b_m_search = mprev;
  1077.     curbuf->b_mb_current = mbp;
  1078.  
  1079.     mp = (info_t *)((char_u *)mp + M_OFFSET);
  1080.     *(char_u *)mp = NUL;            /* set the first byte to NUL */
  1081.  
  1082.     return ((char_u *)mp);
  1083. }
  1084.  
  1085. /*
  1086.  * u_save_line(): allocate memory with u_alloc_line() and copy line 'lnum'
  1087.  * into it.
  1088.  */
  1089.     static char_u *
  1090. u_save_line(lnum)
  1091.     linenr_t    lnum;
  1092. {
  1093.     char_u    *src;
  1094.     char_u    *dst;
  1095.     unsigned    len;
  1096.  
  1097.     src = ml_get(lnum);
  1098.     len = STRLEN(src);
  1099.     if ((dst = u_alloc_line(len)) != NULL)
  1100.     vim_memmove(dst, src, (size_t)(len + 1));
  1101.     return (dst);
  1102. }
  1103.  
  1104. /*
  1105.  * Check if the 'modified' flag is set, or 'ff' has changed (only need to
  1106.  * check the first character, because it can only be "dos", "unix" or "mac").
  1107.  */
  1108.     int
  1109. buf_changed(buf)
  1110.     BUF        *buf;
  1111. {
  1112.     return (buf->b_changed || *buf->b_p_ff != buf->b_start_ffc);
  1113. }
  1114.  
  1115.     int
  1116. curbuf_changed()
  1117. {
  1118.     return (curbuf->b_changed || *curbuf->b_p_ff != curbuf->b_start_ffc);
  1119. }
  1120.